package com.leetcode.LC;

import java.util.Stack;

public class LC844 {
    public boolean backspaceCompare(String S, String T) {

        //更好的方法https://www.bilibili.com/video/BV1wA411b7qZ?p=51
        Stack<Character> stackS = new Stack<Character>();
        Stack<Character> stackT = new Stack<Character>();

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i)!='#'){
                stackS.push(S.charAt(i));
            }else if (!stackS.isEmpty()){
                stackS.pop();
            }
        }
        for (int i = 0; i < T.length(); i++) {
            if (T.charAt(i)!='#'){
                stackT.push(T.charAt(i));
            }else if (!stackT.isEmpty()){
                stackT.pop();
            }
        }
        if(stackS.equals(stackT)){
            return true;
        }
        return false;
    }

    public boolean backspaceCompare2(String S, String T) {

        int i=S.length()-1,j=T.length()-1;
        int BS=0,BT=0;
        while (i>=0||j>=0){
            while (i>=0){
                if(S.charAt(i)=='#'){
                    BS++;
                    i--;
                }else if(BS>0){
                    BS--;
                    i--;
                }else {
                    break;
                }
            }
            while (j>=0){
                if(T.charAt(j)=='#'){
                    BT++;
                    j--;
                }else if(BT>0){
                    BT--;
                    j--;
                }else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new LC844().backspaceCompare2("ab##", "c#d#"));
    }
}
